#pragma once
#include <iostream>
using namespace std;
namespace BSTree
{
	template<class T>
	struct TreeNode
	{
		TreeNode(const T& val)
			:_left(nullptr)
			, _right(nullptr)
			, _val(val)
		{
			;
		}

		TreeNode<T>* _left;
		TreeNode<T>* _right;
		T _val;
	};

	template<class T>
	class BSTree
	{
	public:
		typedef TreeNode<T> Node;
		BSTree()
			:_root(nullptr)
		{
			;
		}

		BSTree(T& val)
		{
			_root = new Node(val);
		}

		~BSTree()
		{
			Destroy(_root);
		}
		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);

			delete root;
		}


		void Insert(const T& val)
		{
			Node* newnode = new Node(val);
			if (_root == nullptr)
			{
				_root = newnode;
				return;
			}
			else
			{
				Node* cur = _root;
				Node* prev = nullptr;
				while (cur)
				{
					if (val < cur->_val)
					{
						prev = cur;
						cur = cur->_left;
					}
					else if (val > cur->_val)
					{
						prev = cur;
						cur = cur->_right;
					}
					else
					{
						return;
					}
				}

				if (val < prev->_val)
				{
					prev->_left = newnode;
				}
				else
				{
					prev->_right = newnode;
				}

			}
		}

		void Erase(const T& val)
		{
			if (_root == nullptr)
			{
				return;
			}
			else
			{
				Node* cur = _root;
				Node* prev = nullptr;
				while (cur)
				{
					if (val < cur->_val)
					{
						prev = cur;
						cur = cur->_left;
					}
					else if (val > cur->_val)
					{
						prev = cur;
						cur = cur->_right;
					}
					else
					{
						if (cur->_left != nullptr)
						{
							Node* prev1 = cur;
							cur = cur->_left;


							while (cur->_right)
							{
								prev1 = cur;
								cur = cur->_right;
							}
							if (val < prev->_val)
							{
								swap(cur->_val, prev->_left->_val);

							}
							else
							{
								swap(cur->_val, prev->_right->_val);
							}
							//if (val < prev->_val)
							//{
							//	if()
							//}
							if (prev1->_left == cur)
							{
								prev1->_left = cur->_left;
							}
							else
							{

								prev1->_right = cur->_left;

							}
							delete cur;
						}
						else if (cur->_right != nullptr)
						{
							Node* prev1 = cur;
							cur = cur->_right;

							while (cur->_left)
							{
								prev1 = cur;
								cur = cur->_left;
							}
							if (val < prev->_val)
							{
								swap(cur->_val, prev->_left->_val);

							}
							else
							{
								swap(cur->_val, prev->_right->_val);
							}

							if (prev1->_right == cur)
							{
								prev1->_right = cur->_right;
							}
							else
							{
								prev1->_left = cur->_right;
							}
							delete cur;
						}
						else
						{
							delete cur;
						}

						return;
					}
				}
			}
		}

		void InOrder()
		{
			inorder(_root);
			cout << endl;
		}
		void inorder(Node* root)
		{
			if (root == nullptr)
				return;
			inorder(root->_left);
			cout << root->_val << " ";
			inorder(root->_right);
		}
		Node* Find(const T& val)
		{
			return find(_root, val);
		}

		Node* find(Node* root, const T& val)
		{
			if (root == nullptr)
				return nullptr;
			if (val > root->_val)
			{
				return find(root->_right, val);
			}
			else if (val < root->_val)
			{
				return find(root->_left, val);
			}
			else
			{
				return root;
			}
		}
		Node* Getroot()
		{
			return _root;
		}
	private:
		Node* _root;
	};


}


namespace kValueTree
{
	template<class K,class V>
	struct TreeNode
	{
		TreeNode(const K& key,const V& val)
			:_left(nullptr)
			, _right(nullptr)
			,_key(key)
			, _val(val)
		{
			;
		}

		TreeNode<K,V>* _left;
		TreeNode<K,V>* _right;
		K _key;
		V _val;
	};

	template<class K,class V>
	class BSTree
	{
	public:
		typedef TreeNode<K,V> Node;
		BSTree()
			:_root(nullptr)
		{
			;
		}

		BSTree(const K& key,const V& val)
		{
			_root = new Node(key,val);
		}

		~BSTree()
		{
			Destroy(_root);
		}
		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);

			delete root;
		}


		void Insert(const K& key,const V& val)
		{
			Node* newnode = new Node(key,val);
			if (_root == nullptr)
			{
				_root = newnode;
				return;
			}
			else
			{
				Node* cur = _root;
				Node* prev = nullptr;
				while (cur)
				{
					if (key < cur->_key)
					{
						prev = cur;
						cur = cur->_left;
					}
					else if (key > cur->_key)
					{
						prev = cur;
						cur = cur->_right;
					}
					else
					{
						cur->_val++;
						return;
					}
				}

				if (key < prev->_key)
				{
					prev->_left = newnode;
				}
				else
				{
					prev->_right = newnode;
				}

			}
		}

		void Erase(const K& key)
		{
			if (_root == nullptr)
			{
				return;
			}
			else
			{
				Node* cur = _root;
				Node* prev = nullptr;
				while (cur)
				{
					if (key < cur->_key)
					{
						prev = cur;
						cur = cur->_left;
					}
					else if (key > cur->_key)
					{
						prev = cur;
						cur = cur->_right;
					}
					else
					{
						if (cur->_left != nullptr)
						{
							Node* prev1 = cur;
							cur = cur->_left;


							while (cur->_right)
							{
								prev1 = cur;
								cur = cur->_right;
							}
							if (key < prev->_key)
							{
								swap(cur->_val, prev->_left->_val);
								swap(cur->_key, prev->_left->_key);

							}
							else
							{
								swap(cur->_val, prev->_right->_val);
								swap(cur->_key, prev->_right->_key);
							}
							//if (val < prev->_val)
							//{
							//	if()
							//}
							if (prev1->_left == cur)
							{
								prev1->_left = cur->_left;
							}
							else
							{

								prev1->_right = cur->_left;

							}
							delete cur;
						}
						else if (cur->_right != nullptr)
						{
							Node* prev1 = cur;
							cur = cur->_right;

							while (cur->_left)
							{
								prev1 = cur;
								cur = cur->_left;
							}
							if (key < prev->_key)
							{
								swap(cur->_val, prev->_left->_val);
								swap(cur->_key, prev->_left->_key);

							}
							else
							{
								swap(cur->_val, prev->_right->_val);
								swap(cur->_key, prev->_right->_key);
							}

							if (prev1->_right == cur)
							{
								prev1->_right = cur->_right;
							}
							else
							{
								prev1->_left = cur->_right;
							}
							delete cur;
						}
						else
						{
							delete cur;
						}

						return;
					}
				}
			}
		}

		void InOrder()
		{
			inorder(_root);
			cout << endl;
		}
		void inorder(Node* root)
		{
			if (root == nullptr)
				return;
			inorder(root->_left);
			cout << root->_key << ":" << root->_val << endl;;
			inorder(root->_right);
		}
		Node* Find(const K& key)
		{
			return find(_root, key);
		}

		Node* find(Node* root, const K& key)
		{
			if (root == nullptr)
				return nullptr;
			if (key > root->_key)
			{
				return find(root->_right, key);
			}
			else if (key < root->_key)
			{
				return find(root->_left, key);
			}
			else
			{
				return root;
			}
		}
		Node* Getroot()
		{
			return _root;
		}
	private:
		Node* _root;
	};


}